《算法设计与分析》 Problem P09. [算法课动态规划] 换硬币

给定面值分别为2，5，7的硬币，每种硬币有无限个，给定一个N，求组成N最少需要的硬币的数量，若无法组成则返回-1.

输入

输入N (1<=N<=100)

输出

输出需要的最少硬币个数

样例

标准输入
`5`
标准输出
`1`

标准输入
`11`
标准输出
`3`

标准输入
`27`
标准输出
`5`

动态规划解决换硬币问题

这道题要求使用动态规划来解决硬币找零问题。给定面值为2、5、7的硬币（每种无限供应），求组成金额N所需的最少硬币数量，若无法组成则返回-1。

解题思路

这是一个典型的”零钱兑换”问题，可以使用动态规划解决：

状态定义：dp[i] 表示组成金额i所需的最少硬币数量
初始化：dp[0] = 0（组成0元不需要硬币），其余初始化为N+1（表示无法组成）
状态转移：对于每个金额i，尝试使用每种硬币（2、5、7）进行更新：
- 如果i >= coin，则dp[i] = min(dp[i], dp[i - coin] + 1)
结果判断：如果dp[N] > N，说明无法组成N，返回-1；否则返回dp[N]

C++代码实现

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int N;
    cin >> N;

    // 初始化dp数组，大小为N+1，初始值设为N+1（表示无法组成）
    vector<int> dp(N + 1, N + 1);
    dp[0] = 0; // 组成0元不需要硬币

    // 硬币面值
    vector<int> coins = {2, 5, 7};

    // 动态规划
    for (int i = 1; i <= N; i++) {
        for (int coin : coins) {
            if (i >= coin) {
                dp[i] = min(dp[i], dp[i - coin] + 1);
            }
        }
    }

    // 如果dp[N] > N，说明无法组成N
    if (dp[N] > N) {
        cout << -1 << endl;
    } else {
        cout << dp[N] << endl;
    }

    return 0;
}

代码说明

初始化：vector<int> dp(N + 1, N + 1) 将dp数组初始化为N+1，表示初始状态下无法组成任何金额（除了0）。
状态转移：对于每个金额i（1到N），尝试使用每种硬币（2、5、7）来更新最小硬币数量。
结果判断：如果dp[N]仍然大于N，说明无法组成金额N，返回-1；否则返回dp[N]。

时间复杂度

时间复杂度：O(N × C)，其中N是目标金额，C是硬币种类数（这里是3）。
空间复杂度：O(N)，需要一个长度为N+1的dp数组。

这个算法在题目给定的N范围（1<=N<=100）内非常高效，可以快速解决问题。

状态转移方程详解

状态转移方程确实是动态规划的核心难点，我来用简单易懂的方式为你详细解释。

什么是状态转移方程？

状态转移方程是动态规划中描述”如何从已知问题的解推导出新问题解”的数学表达式。简单来说，它回答了”当前问题的解，如何利用之前已经解决的小问题的解来计算”。

“状态转移方程的核心在于利用已解问题的结果来解决更大规模的问题，避免重复计算。”

为什么需要状态转移方程？

想象一下，如果我们要计算斐波那契数列的第100项，直接递归计算会非常低效，因为会重复计算很多子问题。而动态规划通过状态转移方程，让我们能高效地计算：

F(0) = 0
F(1) = 1
F(2) = F(1) + F(0) = 1
F(3) = F(2) + F(1) = 2
F(4) = F(3) + F(2) = 3
…

这里的状态转移方程是：F(n) = F(n-1) + F(n-2)

状态转移方程的组成部分

状态（State）：问题的某个特定点或阶段。例如在换硬币问题中，dp[i]表示”组成金额i所需的最少硬币数”。
决策（Decision）：在某个状态下，我们选择做什么。例如在换硬币问题中，我们选择使用哪种面值的硬币。
状态转移方程：描述如何从已知状态转移到新状态的公式。例如在换硬币问题中，dp[i] = min(dp[i], dp[i - coin] + 1)。

换硬币问题中的状态转移方程详解

让我们回到题目：给定面值2、5、7的硬币，求组成N最少需要的硬币数量。

1. 定义状态

dp[i] = 组成金额i所需的最少硬币数量

2. 状态转移方程

dp[i] = min(dp[i], dp[i - 2] + 1, dp[i - 5] + 1, dp[i - 7] + 1)
- 如果i ≥ 2，我们可以考虑用1个2元硬币，那么需要的硬币数是dp[i-2] + 1
- 如果i ≥ 5，我们可以考虑用1个5元硬币，那么需要的硬币数是dp[i-5] + 1
- 如果i ≥ 7，我们可以考虑用1个7元硬币，那么需要的硬币数是dp[i-7] + 1
- 然后取这三种情况中的最小值

3. 为什么这样设计？

这个方程利用了”最优子结构”：组成金额i的最少硬币数，可以通过组成更小金额的最优解来构建。
例如：要组成金额10，我们考虑：
- 用1个2元硬币：需要1 + 组成8元的最少硬币数
- 用1个5元硬币：需要1 + 组成5元的最少硬币数
- 用1个7元硬币：需要1 + 组成3元的最少硬币数
- 然后取这三种情况中的最小值

4. 一个具体例子

假设我们要计算组成金额8的最少硬币数：

dp[8] = min(dp[8], dp[6]+1, dp[3]+1, dp[1]+1)
我们需要先知道dp[6]、dp[3]和dp[1]的值

计算过程：

dp[0] = 0（基础情况）
dp[2] = 1（1个2元硬币）
dp[4] = 2（2个2元硬币）
dp[5] = 1（1个5元硬币）
dp[6] = min(dp[6], dp[4]+1, dp[1]+1, dp[-1]+1) = min(∞, 2+1, ∞, ∞) = 3（3个2元硬币）
dp[3] 无法组成（因为最小硬币是2，3-2=1无法组成），所以dp[3] = ∞
dp[1] 无法组成，所以dp[1] = ∞
dp[8] = min(∞, dp[6]+1, dp[3]+1, dp[1]+1) = min(∞, 3+1, ∞, ∞) = 4（4个2元硬币）